﻿// 0909train03.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <vector>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <unordered_map>
#include <unordered_set>

using namespace std;


/*
 输入描述
第一行输入表示基站的个数 N，其中 0 < N <= 20
第二行输入表示具备光纤直连条件的基站对的数目 M，其中 0 < M < N * (N - 1) / 2
第三行开始连续输入 M 行数据，格式为 X Y Z P，
其中 X Y 表示基站的编号，0 < X <= N， 0 < Y <= N 且 X 不等于 Y， Z 表示在 X Y 之间架设光纤的成本，
其中 0 < Z < 100，P 表示是否已存在光纤连接，0 表示未连接， 1 表示已连接。

输出描述
如果给定条件，可以建设成功互联互通的 5G 网络，则输出最小的建设成本，
如果给定条件，无法建设成功互联互通的 5G 网络，则输出-1

示例1
输入
3
3
1 2 3 0
1 3 1 0
2 3 5 0
输出
4
只需要在 1,2 以及 2,3 基站之间铺设光纤，其成本为 3+1=4

示例2
输入
3
1
1 2 5 0
输出
-1
3 基站无法与其他基站连接，输出-1

示例3
输入
3
3
1 2 3 0
1 3 1 0
2 3 5 1
输出
1
2,3 基站已有光纤相连，只有要再 1,3 站点 2 向铺设，其成本为 1
 */
class Solution02
{
public:
    struct Node
    {
        int x, y, val, complete;
        Node() = default;
        Node(int x, int y, int val, int complete) :x(x), y(y), val(val), complete(complete) {};
    };

    int findParent(int x)
    {
        while (parents[x] != x)
            x = parents[x];

        return x;
    }

    void unionSet(int x, int y)
    {
        parents[findParent(x)] = findParent(y);
        //unionSet
    }

    Solution02(vector<vector<int>>&num_vec, int total)
    {
        //编号从1开始
        parents.resize(total + 1);
        for (int i=0; i<=total; i++)
        {
            parents[i] = i;
        }

        vector<Node>edge_v;
        int edge_num = 0;
        for (auto&min_vec:num_vec)
        {
            int x = min_vec[0], y = min_vec[1], val = min_vec[2], complete = min_vec[3];
            if (complete ==1)
            {
                if (findParent(x)!=findParent(y))
                {
                    unionSet(x, y);
                    edge_num += 1;
                }
                continue;
            }
            Node node(x,y,val, complete);
            edge_v.push_back(node);
        }

        sort(edge_v.begin(), edge_v.end(), [](Node&a, Node&b)
        {
        	return a.val < b.val;
        });

        int result = 0;
        for (int i=0; i<edge_v.size(); i++)
        {
            Node curr_node = edge_v[i];
            if (findParent(curr_node.x)!= findParent(curr_node.y))
            {
                unionSet(curr_node.x, curr_node.y);
                result += curr_node.val;
                edge_num += 1;
            }
            
            if (edge_num==total-1)
            {
                break;
            }
        }

        if (edge_num==total-1)
        {
            cout << result;
            return;
        }
        cout << -1;
        //Solution02
    }
private:
    vector<int>parents;
};


/*
 用一个数组A代表程序员的工作能力，公司想通过结对编程的方式提高员工的能力，
 假设结对后的能力为两个员工的能力之和，求一共有多少种结对方式使结对后能力为N

输入描述
第一行为员工的总人数，取值范围[1,1000]
第二行为数组A的元素，每个元素的取值范围[1,1000]
第三行为N的值，取值范围[1,1000]

输出描述
满足结对后能力为N的结对方式总数。

输入
5
1 2 2 2 3
4
输出
4
 */
class Solution01
{
public:
    Solution01(vector<int>&num_vec, int target)
    {
        unordered_map<int, long long>count_map;

        for (auto&num:num_vec)
        {
            count_map[num] += 1;
        }

        long long result = 0;
        for (auto&num_item:count_map)
        {
            int curr_num = num_item.first;
            long long curr_count = num_item.second;
            int team_num = target - curr_num;

            if (curr_num< team_num)
            {
                if (count_map.count(team_num)>0)
                {
                    result += curr_count * count_map.at(team_num);
                }
            }
            else if (curr_num== team_num)
            {
                result += curr_count * (curr_count - 1) / 2;
            }

        }
        cout << result;
        //Solution01
    }
};

int main()
{
	{
/*
3
3
1 2 3 0
1 3 1 0
2 3 5 1
*/
        int total, v_size;
        cin >> total >> v_size;

        vector<vector<int>>num_vec;
        for (int i=0; i<v_size; i++)
        {
            vector<int>min_vec(4);
            cin >> min_vec[0] >> min_vec[1] >> min_vec[2] >> min_vec[3];
            num_vec.push_back(min_vec);
        }

        Solution02 solu(num_vec, total);

        return 0;
	}
	int v_size;
    cin >> v_size;

    vector<int>num_vec(v_size);
    for (int i=0; i<v_size; i++)
    {
        cin >> num_vec[i];
    }

    int target;
    cin >> target;

    Solution01 solu(num_vec, target);



}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
